# -*- coding:utf-8 -*-

import csv
import itertools
import math
import random
import time
import copy

global GK

GK = 4000

global GT

GT = 30

global N1, N1s, N1t
# N1 是繁殖时找的节点比例 N1s 是繁殖时对比的节点比例
N1 = 0.1
N1s = 0.5
N1t = 1

global N2
# N2 是突变时的节点比例 N2s 是突变时对比的节点比例
N2 = 0.1
N2s = 0.5

# 7.15 new V0.5 copyright by liufei

# 把所有电商订单信息抽出来

# id Spot_id Site_id Num

Forder = {}

reader = csv.reader(file('new_4.csv', 'rU'))
for line in reader:  # 配送点id，网点id，网点需要送至改配送点的电商包裹量
    Forder[line[0]] = [line[1], line[2], line[3]]

# 把所有O2O订单信息抽出来

# id spot_id shop_id Pick_time Delivery_time Num

Eorder = {}

reader = csv.reader(file('new_5.csv', 'rU'))
for line in reader:  # 配送点id，商户id，到商户的领取时间（e.g. 11:00），送达至消费者的最晚时间（e.g. 20:00），订单所含包裹量
    Eorder[line[0]] = [line[1], line[2], line[3], line[4], line[5]]

# print order

# 所有订单

Order = dict(Forder, **Eorder)

# 把所有网点信息抽出来

# id Lng Lat

site = {}

reader = csv.reader(file('new_1.csv', 'rU'))
for line in reader:  # 网点经度，网点纬度
    site[line[0]] = [line[1], line[2]]

# 把所有配送点信息抽出来

# id Lng Lat

spot = {}

reader = csv.reader(file('new_2.csv', 'rU'))
for line in reader:  # 配送点经度，配送点纬度
    spot[line[0]] = [line[1], line[2]]

# 把所有商店信息抽出来

# id Lng Lat

shop = {}

reader = csv.reader(file('new_3.csv', 'rU'))
for line in reader:  # 商户经度，商户纬度
    shop[line[0]] = [line[1], line[2]]

# 所有取货点
Point = dict(site, **shop)


# 聚类
def kmeans(k):
    sites = site.keys()
    shops = shop.keys()

    ids = random.sample(site.keys(), k)

    Cs = range(k)
    for i in range(k):
        Cs[i] = []

    us = range(k)

    i = 0
    for id in ids:
        us[i] = [Point[id][0], Point[id][1]]
        i += 1

    temp = us

    while (1):
        for i in range(k):
            Cs[i] = []

        for id in site.keys():
            mindis = 10000000
            for i in range(k):
                dis = tdistance(us[i][0], us[i][1], Point[id][0], Point[id][1])
                if dis < mindis:
                    mindis = dis
                    mini = i
            Cs[mini].append(id)

        for id in shop.keys():
            mindis = 10000000
            for i in range(k):
                dis = tdistance(us[i][0], us[i][1], Point[id][0], Point[id][1])
                if dis < mindis:
                    mindis = dis
                    mini = i
            Cs[mini].append(id)

        for i in range(k):
            sum1 = 0
            sum2 = 0
            for id in Cs[i]:
                sum1 += float(Point[id][0])
                sum2 += float(Point[id][1])
            us[i][0] = sum1 / len(Cs[i])
            us[i][1] = sum2 / len(Cs[i])

        if us == temp:
            break
        else:
            temp = us
    return Cs


# 从取货点找订单
def getorders(C):
    orders = []
    for id in C:
        for id2 in Order.keys():
            if Order[id2][1] == id:
                orders.append(id2)
    return orders


# 计算距离
def distance(lat1, lat2, lng1, lng2):
    lat1 = float(lat1)
    lat2 = float(lat2)
    lng1 = float(lng1)
    lng2 = float(lng2)

    def delt(x, y):
        return (x - y) / 2

    def angle(x):
        return math.pi * x / 180

    s2lat = math.pow(math.sin(angle(delt(lat1, lat2))), 2)
    clat1 = math.cos(angle(lat1))
    clat2 = math.cos(angle(lat2))
    s2lng = math.pow(math.sin(angle(delt(lng1, lng2))), 2)

    return 2 * 6378137 * math.asin(math.sqrt(s2lat + clat1 * clat2 * s2lng))


def givelnglat(S):
    if S.find('A') == 0:
        lng = float(site[S][0])
        lat = float(site[S][1])
    elif S.find('B') == 0:
        lng = float(spot[S][0])
        lat = float(spot[S][1])
    elif S.find('S') == 0:
        lng = float(shop[S][0])
        lat = float(shop[S][1])
    else:
        return -1
    return [lng, lat]


def sdistance(s1, s2):
    l1 = givelnglat(s1)
    l2 = givelnglat(s2)
    return distance(l1[1], l2[1], l1[0], l2[0])


def tdistance(lat1, lng1, lat2, lng2):
    # type: (object, object, object, object) -> object
    lat1 = float(lat1)
    lat2 = float(lat2)
    lng1 = float(lng1)
    lng2 = float(lng2)
    return math.sqrt((lat1 - lat2) ** 2 + (lng1 - lng2) ** 2)


# 算时间差

def timedif(time1, time2):
    time1 = time1.split(':')
    time1 = int(time1[0]) * 60 + int(time1[1])
    time2 = time2.split(':')
    time2 = int(time2[0]) * 60 + int(time2[1])
    return time2 - time1


def addtime(time1, timedif):
    time1 = time1.split(':')
    time1 = int(time1[0]) * 60 + int(time1[1])
    time2 = time1 + int(timedif)
    nums = divmod(time2, 60)
    return str(nums[0]) + ':' + str(nums[1])


# 判断订单类型

def ordertype(id):
    # print id
    if id.find('E') == 0:
        return 0
    elif id.find('F') == 0:
        return 1
    else:
        return -1


# 计算服务时长
def getservetime(id):
    if id.find('E') == 0:
        x = int(Order[id][4])
    elif id.find('F') == 0:
        x = int(Order[id][2])
    else:
        print 'servetime error'
        return -1
    return int(round(3 * math.sqrt(x) + 5))


# 按时间给O2O订单排序
def sortontime(orders):
    print orders
    dic = {}
    neworders = []
    for id in orders:
        dic[id] = timedif('8:00', Order[id][2])
    dic = sorted(dic.iteritems(), key=lambda d: d[1], reverse=False)
    for i in dic:
        neworders.append(i[0])
    # print neworders
    return neworders


# 格式化序列

def getformatplan(plan):
    i = 0
    formatplan = []
    while (1):
        if i > len(plan) - 1:
            break
        id = plan[i][0]
        type = plan[i][1]
        # print i
        if ordertype(id) == 0:
            if i == 0:
                # 找到最近的网点
                mindis = 1000000
                for siteid in site.keys():
                    dis = sdistance(Order[id][1], siteid)
                    if dis < mindis:
                        mindis = dis
                mintime = int(round(mindis / 250))
                arrtime = mintime
            else:
                if type == 0:
                    # print id
                    # print Order[id]
                    dis = sdistance(formatplan[i - 1][0], Order[id][1])
                else:
                    dis = sdistance(formatplan[i - 1][0], Order[id][0])
                distime = int(round(dis / 250))
                arrtime = formatplan[i - 1][2] + distime
            amount = Order[id][4]
            if type == 0:
                addr = Order[id][1]
                depatime = max(arrtime, timedif('8:00', Order[id][2]))
                amount = '+' + amount
            else:
                addr = Order[id][0]
                servetime = getservetime(id)
                depatime = arrtime + servetime
                amount = '-' + amount
        else:
            if i == 0:
                arrtime = 0
            else:
                if type == 0:
                    dis = sdistance(formatplan[i - 1][0], Order[id][1])
                else:
                    dis = sdistance(formatplan[i - 1][0], Order[id][0])
                distime = int(round(dis / 250))
                arrtime = formatplan[i - 1][2] + distime
            amount = Order[id][2]
            if type == 0:
                addr = Order[id][1]
                depatime = arrtime
                amount = '+' + amount
            else:
                addr = Order[id][0]
                servetime = getservetime(id)
                depatime = arrtime + servetime
                amount = '-' + amount

        formatplan.append([addr, arrtime, depatime, amount, id])
        i += 1
    return formatplan


# 移动节点，i位置的移动到j之后
def movenode(plan, i, j):
    tempnode = plan[i][:]
    del plan[i]
    plan.insert(j, tempnode)
    return plan


def movenode2(plan, i, j):
    tempnode = plan[i][:]
    plan[i] = plan[j][:]
    plan[j] = tempnode
    return plan


# 考察负重
def isgok(formatplan):
    n = 0
    for node in formatplan:
        amount = node[3]
        if '+' in amount:
            n += int(amount[1:])
        else:
            n -= int(amount[1:])
        if n > 140:
            return -1
    return 0


# 考察最后一个结点的到达时间有没有超过8点
def ist1ok(formatplan):
    id = formatplan[-1][-1]
    if ordertype(id) == 1:
        if formatplan[-1][2] <= 720:
            return 0
        else:
            return -1
    else:
        return 0


# 考察最后一个结点的到达时间有没有超过8点
def ist1ok2(formatplan):
    id = formatplan[-1][-1]
    if ordertype(id) == 1:
        if formatplan[-1][2] <= 800:
            return 0
        else:
            return -1
    else:
        return 0


# 考察时间窗/新方案废弃这种考察
def ist2ok(formatplan):
    for node in formatplan:
        id = node[4]
        if ordertype(id) == 0:
            if '+' in node[3]:
                arrtime = addtime('8:00', node[1])
                # print Order[id][2]
                # print arrtime
                if timedif(arrtime, Order[id][2]) < 0:
                    return node
            else:
                arrtime = addtime('8:00', node[1])
                # print Order[id][3]
                # print arrtime
                arrtime = addtime('8:00', node[1])
                if timedif(arrtime, Order[id][3]) < 0:
                    return node
    return 0


# 考察plan的顺序
def isturnok(plan):
    turnget = {}
    turndeli = {}
    for i in range(0, len(plan)):
        type = plan[i][1]
        id = plan[i][0]
        #		print type
        #		print id
        if type == 0:
            turnget[id] = i
        elif type == 1:
            turndeli[id] = i
        else:
            'turnokerror'
    # print turnget
    # print turndeli
    for id in turnget.keys():
        if turnget[id] > turndeli[id]:
            return -1
    return 0


# 得到耗时
def getscore(formatplan):
    score = formatplan[-1][2]
    # if isgok(formatplan) == 0 and ist1ok(formatplan) == 0:
    if isgok(formatplan) == 0 and ist1ok2(formatplan) == 0:
        for node in formatplan:
            id = node[-1]
            if ordertype(id) == 0:
                # 是取货
                if '+' in node[3]:
                    diftime = node[1] - timedif('8:00', Order[id][2])
                    if diftime > 0:
                        score += diftime * 5
                else:
                    diftime = node[1] - timedif('8:00', Order[id][3])
                    if diftime > 0:
                        score += diftime * 5
        return score
    else:
        print 'getscore error'
        return -1


# 得到等待时间
def getwaitscore(formatplan):
    waittime = 0
    for i in range(0, len(formatplan)):
        id = formatplan[i][-1]  # 订单号
        idname = formatplan[i][0]  # 对应代号
        if i != 0:
            if ordertype(id) == 0:  # O2O
                if '+' in formatplan[i][3]:
                    arrtime = timedif('8:00', Order[id][2])  # 到达O2O时间
                    idlastname = formatplan[i - 1][0]  # 获取上一个点代号
                    dis = sdistance(idname, idlastname)  # 上一个点到这个点的路上时间
                    transtime = int(round(dis / 250))
                    leavetime = formatplan[i - 1][2]  # 上一个点离开时间
                    waittime = arrtime - leavetime - transtime + waittime
        i += 1
    return waittime


def findexplans(plan1, plan2):
    # 先计算原来的
    plan1score = getscore(getformatplan(plan1))
    if plan2 != []:
        plan2score = getscore(getformatplan(plan2))
    else:
        plan2score = 0

    # 先用1给2一个订单
    temp1 = plan1[:]
    temp2 = plan2[:]
    # nodes = random.sample(temp1, 1) # 随机产生一个节点
    # nodes = random.sample(temp1[len(temp1)/2 : ], 1) # 随机产生一个节点
    nodes = temp1[-1]  # 节点为路径的倒数第二站，即最后一个取货点
    # nodes = random.sample(temp1[-7:-2], 1)
    # nodes = nodes[0]
    # print nodes[0]
    # chosenid = nodes[0][0]  # chosenid = nodes[0]
    chosenid = nodes[0]
    # if ordertype(chosenid) != 0:                    # 只对O2O订单
    #     return -1
    # print chosenid
    temp1.remove([chosenid, 0])
    temp1.remove([chosenid, 1])
    if temp1 == []:
        temp1score = 0
    else:
        temp1formatplan = getformatplan(temp1)
        temp1score = getscore(temp1formatplan)

    # O2O订单
    if ordertype(chosenid) == 0:
        # 取货节点
        for i in range(len(temp2) / 2, len(temp2)):
            # for i in range(len(temp2) - 8, len(temp2)):
            #     if i != len(temp2) - 2:     # 同样取倒数第二个节点，即最后一个取货点
            #         continue
            temp2p = temp2[:]
            if i == 0:
                temp2p.insert(0, [chosenid, 0])
            else:
                id = temp2p[i][0]
                if ordertype(id) != 0:
                    continue  # 只对O2O订单
                type = temp2p[i][1]
                if type == 0:
                    addr = Order[id][1]
                else:
                    addr = Order[id][0]
                dis = sdistance(addr, Order[chosenid][1])
                # print chosenid
                # print id
                # print dis
                # 还是判断两个值，一个是到达距离不宜太远（GK），// 一个是迟到时间不宜太长（GT）
                if dis < 5000:
                    if abs(timedif(Eorder[chosenid][2], Eorder[id][2])) < 60:
                        # if sdistance(Eorder[chosenid][0], Eorder[chosenid][1]) > 10000:
                        #     if sdistance(Eorder[id][0], Eorder[id][1]) > 10000:
                        #         print abs(timedif(Eorder[chosenid][2], Eorder[id][2]))
                        temp2p.insert(i, [chosenid, 0])
                        #     else:
                        #         continue
                        # else:
                        #     continue
                    else:
                        continue
                else:
                    continue
            # 送货
            for j in range(i + 1, len(temp2) + 1):
                temp2q = temp2p[:]
                id = temp2q[j][0]
                type = temp2q[j][1]
                if type == 0:
                    addr = Order[id][1]
                else:
                    addr = Order[id][0]
                dis = sdistance(addr, Order[chosenid][0])
                # print dis
                # 还是判断两个值，一个是到达距离不宜太远（GK），//一个是迟到时间不宜太长（GT）
                # if dis < GK:
                if dis < 2000:
                    temp2q.insert(j, [chosenid, 1])
                    temp2formatplan = getformatplan(temp2q)
                    # if isgok(temp2formatplan) == 0 and ist1ok(temp2formatplan) == 0:
                    if isgok(temp2formatplan) == 0 and ist1ok2(temp2formatplan) == 0:
                        temp2score = getscore(temp2formatplan)
                        # print temp1score, temp2score, plan1score, plan2score
                        # print temp2score + temp1score, plan1score + plan2score
                        if (temp2score + temp1score) < (plan1score + plan2score):
                            return [temp1, temp2q]
                            # else:
                            #     if 1.0 * random.random() < 0.02:
                            #         if (temp2score + temp1score) < 1.005 * (plan1score + plan2score):
                            #             return [temp1, temp2q]
                else:
                    continue

    # 电商订单
    else:
        # for i in range(0, len(temp2)):
        for i in range(len(temp2) / 2, len(temp2)):
            temp2p = temp2[:]
            if i == 0:
                temp2p.insert(0, [chosenid, 0])
            else:
                id = temp2p[i - 1][0]
                type = temp2p[i - 1][1]
                if type == 0:
                    addr = Order[id][1]
                else:
                    addr = Order[id][0]
                dis = sdistance(addr, Order[chosenid][1])
                # 到达距离不宜太远（GK）
                if dis < GK:
                    temp2p.insert(i, [chosenid, 0])
                else:
                    continue
            for j in range(i + 1, len(temp2) + 1):
                temp2q = temp2p[:]

                id = temp2q[j - 1][0]
                type = temp2q[j - 1][1]
                if type == 0:
                    addr = Order[id][1]
                else:
                    addr = Order[id][0]
                dis = sdistance(addr, Order[chosenid][0])
                # 到达距离不宜太远（GK）
                if dis < GK:
                    temp2q.insert(j, [chosenid, 1])
                    temp2formatplan = getformatplan(temp2q)
                    if isgok(temp2formatplan) == 0 and ist1ok2(temp2formatplan) == 0:
                        temp2score = getscore(temp2formatplan)
                        if (temp2score + temp1score) < (plan1score + plan2score):
                            return [temp1, temp2q]
                        else:
                            if 1.0 * random.random() < 0.02:
                                if (temp2score + temp1score) < 1.005 * (plan1score + plan2score):
                                    return [temp1, temp2q]

    return -1


def findexplans2(plan1, plan2):
    # 先计算原来的
    plan1score = getscore(getformatplan(plan1))
    plan2score = getscore(getformatplan(plan2))

    # 先用1给2一个订单
    temp1 = plan1[:]
    temp2 = plan2[:]
    # print 'plan1:', plan1
    # print 'plan2:', plan2
    nodes = random.sample(temp1, 1)  # 随机产生一个节点
    chosenid = nodes[0][0]  # chosenid = nodes[0]

    # O2O订单
    if ordertype(chosenid) == 0:
        # 取货节点
        # for i in range(0, len(temp2)):
        for i in range(len(temp2) / 2, len(temp2)):
            temp1p = temp1[:]
            temp2p = temp2[:]
            chosenid2 = temp2p[i][0]
            j = temp2p.index([chosenid2, 0])
            jj = temp2p.index([chosenid2, 1])
            # temp2p = temp2[:]
            if i == 0:
                temp1p[temp1p.index([chosenid, 0])] = [chosenid2, 0]
                temp2p[j] = [chosenid, 0]
            else:
                id = temp2p[j - 1][0]
                type = temp2p[j - 1][1]
                if type == 0:
                    addr = Order[id][1]
                else:
                    addr = Order[id][0]
                dis = sdistance(addr, Order[chosenid][1])
                # 还是判断两个值，一个是到达距离不宜太远（GK），// 一个是迟到时间不宜太长（GT）
                if dis < GK:
                    # temp2p.insert(i, [chosenid, 0])
                    temp1p[temp1p.index([chosenid, 0])] = [chosenid2, 0]
                    temp2p[j] = [chosenid, 0]
                else:
                    continue
                    # 送货
                    # for j in range(i + 1, len(temp2) + 1):
                    #     temp2q = temp2[:]
            id = temp2p[jj - 1][0]
            type = temp2p[jj - 1][1]
            if type == 0:
                addr = Order[id][1]
            else:
                addr = Order[id][0]
            dis = sdistance(addr, Order[chosenid][0])
            # 还是判断两个值，一个是到达距离不宜太远（GK），//一个是迟到时间不宜太长（GT）
            if dis < GK:
                temp1p[temp1p.index([chosenid, 1])] = [chosenid2, 1]
                temp2p[jj] = [chosenid, 1]
                temp1formatplan = getformatplan(temp1p)
                temp2formatplan = getformatplan(temp2p)
                if isgok(temp1formatplan) == 0 and ist1ok2(temp1formatplan) == 0:
                    if isgok(temp2formatplan) == 0 and ist1ok2(temp2formatplan) == 0:
                        temp1score = getscore(temp1formatplan)
                        temp2score = getscore(temp2formatplan)
                        if (temp2score + temp1score) < (plan1score + plan2score):
                            return [temp1p, temp2p]
                        else:
                            if 1.0 * random.random() < 0.02:
                                if (temp2score + temp1score) < 1.005 * (plan1score + plan2score):
                                    return [temp1p, temp2p]
            else:
                continue

    # 电商订单
    else:
        # for i in range(0, len(temp2)):
        for i in range(len(temp2) / 2, len(temp2)):
            temp1p = temp1[:]
            temp2p = temp2[:]
            chosenid2 = temp2p[i][0]
            # print i
            # print chosenid2
            # print temp2p
            # print len(temp2p)
            j = temp2p.index([chosenid2, 0])
            jj = temp2p.index([chosenid2, 1])
            if i == 0:
                temp1p[temp1p.index([chosenid, 0])] = [chosenid2, 0]
                temp2p[j] = [chosenid, 0]
            else:
                id = temp2p[j - 1][0]
                type = temp2p[j - 1][1]
                if type == 0:
                    addr = Order[id][1]
                else:
                    addr = Order[id][0]
                dis = sdistance(addr, Order[chosenid][1])
                # 到达距离不宜太远（GK）
                if dis < GK:
                    temp1p[temp1p.index([chosenid, 0])] = [chosenid2, 0]
                    temp2p[j] = [chosenid, 0]
                else:
                    continue

            id = temp2p[jj - 1][0]
            type = temp2p[jj - 1][1]
            if type == 0:
                addr = Order[id][1]
            else:
                addr = Order[id][0]
            dis = sdistance(addr, Order[chosenid][0])
            # 到达距离不宜太远（GK）
            if dis < GK:
                temp1p[temp1p.index([chosenid, 1])] = [chosenid2, 1]
                temp2p[jj] = [chosenid, 1]
                temp1formatplan = getformatplan(temp1p)
                temp2formatplan = getformatplan(temp2p)
                if isgok(temp1formatplan) == 0 and ist1ok2(temp1formatplan) == 0:
                    if isgok(temp2formatplan) == 0 and ist1ok2(temp2formatplan) == 0:
                        temp1score = getscore(temp1formatplan)
                        temp2score = getscore(temp2formatplan)
                        if (temp2score + temp1score) < (plan1score + plan2score):
                            return [temp1p, temp2p]
                        else:
                            if 1.0 * random.random() < 0.02:
                                if (temp2score + temp1score) < 1.005 * (plan1score + plan2score):
                                    return [temp1p, temp2p]

    return -1


# 繁殖

def reproduce(plans):
    num1 = 0
    num2 = 0
    plans.sort(key=lambda plan: len(plan))
    js = random.sample(range(0, int(len(plans) * N1t)), max(1, int(len(plans) * 0.1)))
    # js = [674, 787, 481, 574, 413, 887, 200, 886]
    for j in js:
        if j < len(plans):
            num = onereproduce(j, plans)  # 对于plans1中的每一个plan1，都选取一个合适的plan2交叉
            if num != -1:
                num1 += 1
                num2 += num

    return [num1, num2]


def reproduce2(plans):
    num1 = 0
    plans.sort(key=lambda plan: len(plan))
    js = random.sample(range(0, int(len(plans) * N1t)), max(1, int(len(plans) * N1)))
    for j in js:
        if j < len(plans):
            num = onereproduce2(j, plans)  # 对于plans1中的每一个plan1，都选取一个合适的plan2交叉
            if num != -1:
                num1 += 1

    return num1


def onereproduce(i, plans):
    num2 = 0
    js = random.sample(range(0, int(len(plans))), max(1, int(len(plans) * N1s)))
    # js = [674, 787, 481, 574, 413, 887, 200, 886]
    for j in js:
        # j = len(plans) - 1 - j
        if i != j and j < len(plans):
            if plans[i] != []:
                explans = findexplans(plans[i], plans[j])
                if explans != -1:
                    plans[i] = explans[0]
                    plans[j] = explans[1]

                    if plans[i] != []:
                        plan = onevariation(plans[i])
                        if plan != -1:
                            plans[i] = plan
                            num2 += 1

                    if plans[j] != []:
                        plan = onevariation(plans[j])
                        if plan != -1:
                            plans[j] = plan
                            num2 += 1

                    if len(plans) > 1000:  # 保持plan个数在145个不变
                        if [] in plans:
                            plans.remove([])

                    return num2

    return -1


def onereproduce2(i, plans):
    js = random.sample(range(0, len(plans)), max(1, int(len(plans) * N1s)))
    for j in js:
        j = len(plans) - 1 - j
        if i != j and j < len(plans):
            if plans[i] != [] and plans[j] != []:
                explans = findexplans2(plans[i], plans[j])
                if explans != -1:
                    plans[i] = explans[0]
                    plans[j] = explans[1]
                    return 0

    return -1


# 变异
def onevariation(plan):
    oldscore = getscore(getformatplan(plan))
    ii = random.sample(range(0, len(plan)), max(1, int(len(plan) * N2)))
    jj = random.sample(range(0, len(plan)), max(1, int(len(plan) * N2s)))
    for i in ii:
        for j in jj:
            if i != j:
                temp = plan[:]
                # print temp,i,j
                # if temp[i][0] == ['F6366']:
                # print getformatplan(temp)
                # print getscore(formatplan(temp))
                # print oldscore
                temp = movenode(temp, i, j)  # 把节点i的位置移动到j之后
                # print temp
                if isturnok(temp) != -1:  # 考察顺序是否合理
                    #	print temp
                    formatplan = getformatplan(temp)
                    # print formatplan
                    if isgok(formatplan) == 0 and ist1ok(formatplan) == 0:
                        score = getscore(formatplan)
                        if score < oldscore:
                            plan = temp
                            return plan
    return -1


# 变异 2.0
def onevariation2(plan):
    oldscore = getscore(getformatplan(plan))
    lengthOfPlan = len(plan)
    if int(len(plan)) - 8 >= 0:
        # for m in range(int(len(plan)) / 2 - 8):
        for m in range(int(lengthOfPlan) - 8):
            if m % 2 == 0:
                for i in range(m, m + 2):
                    for j in range(m + 2, m + 6):
                        # if i != j:
                        temp = plan[:]
                        temp = movenode2(temp, i, j)  # 把节点i与节点j换位
                        # print temp
                        if isturnok(temp) != -1:  # 考察顺序是否合理
                            #	print temp
                            formatplan = getformatplan(temp)
                            # print formatplan
                            if isgok(formatplan) == 0 and ist1ok(formatplan) == 0:
                                score = getscore(formatplan)
                                if score < oldscore:
                                    plan = temp
                                    return plan
                                else:
                                    if 1.0 * random.random() < 0.005:
                                        if score < 1.01 * oldscore:
                                            plan = temp
                                            return plan
    return -1


# 变异 3.0
def onevariation3(plan):
    oldscore = getscore(getformatplan(plan))
    lengthOfPlan = len(plan)
    js = random.sample(range(0, int(lengthOfPlan)), int(lengthOfPlan))
    plan1 = plan[:]
    i = 0
    for j in js:
        plan1[i] = plan[j]
        i += 1

    if isturnok(plan1) != -1:  # 考察顺序是否合理
        formatplan = getformatplan(plan1)
        if isgok(formatplan) == 0 and ist1ok(formatplan) == 0:
            score = getscore(formatplan)
            if score < oldscore:
                plan = plan1
                return plan
            else:
                # if 1.0 * random.random() < 0.005:
                if score < 1.01 * oldscore:
                    plan = plan1
                    return plan
    return -1


# 变异 4.0 ： 等待时间优化的变异
def onevariationwait(plan):
    oldscore = getscore(getformatplan(plan))
    oldwaitscore = getwaitscore(getformatplan(plan))
    ii = random.sample(range(0, len(plan)), max(1, int(len(plan) * N2)))
    jj = random.sample(range(0, len(plan)), max(1, int(len(plan) * N2s)))
    for i in ii:
        for j in jj:
            if i != j:
                temp = plan[:]
                movenode(temp, i, j)
                # print temp
                if isturnok(temp) != -1:
                    # print temp
                    formatplan = getformatplan(temp)
                    # print formatplan
                    if isgok(formatplan) == 0 and ist1ok(formatplan) == 0:
                        score = getscore(formatplan)
                        waitscore = getwaitscore(formatplan)
                        if score <= 1 * oldscore:
                            if waitscore >= oldwaitscore:
                                plan = temp
                                return plan


def inheritance(plans):
    allscore = 0
    beginscore = 0

    for plan in plans:
        if plan != []:
            beginscore += getscore(getformatplan(plan))

    nums = reproduce(plans)  # 交叉+变异操作，返回交叉次数和变异次数
    lenofplans = 0
    for plan in plans:
        if plan != []:
            allscore += getscore(getformatplan(plan))
            lenofplans += 1

    print 'success repro:' + str(nums[0])
    print 'success varia:' + str(nums[1])
    print 'now score:' + str(allscore)
    print 'better:' + str(beginscore - allscore)
    # print 'length:' + str(len(plans))
    print 'length:' + str(lenofplans)
    return allscore


def inheritance2(plans):
    num2 = 0
    allscore = 0
    beginscore = 0

    for plan in plans:
        if plan != []:
            beginscore += getscore(getformatplan(plan))

    num1 = reproduce2(plans)

    for i in range(int(len(plans))):
        if 1.0 * random.random() < 0.1:
            if plans[i] != []:
                # print plans[i]
                plan = onevariation2(plans[i])
                if plan != -1:
                    plans[i] = plan
                    num2 += 1

    for plan in plans:
        if plan != []:
            allscore += getscore(getformatplan(plan))

    print 'success repro2:' + str(num1)
    print 'success varia2:' + str(num2)
    print 'better2:' + str(beginscore - allscore)
    return allscore


def inheritancewait(plans):
    beginscore = 0
    allscore = 0

    for plan in plans:
        if plan != []:
            beginscore += getscore(getformatplan(plan))

    chance = 0.5
    num3 = 0
    for i in range(0, len(plans)):
        plan = plans[i]
        if random.random() < chance:
            # print plan
            if plan != []:
                newplan = onevariationwait(plan)
                if newplan != -1:
                    plans[i] = newplan
                    num3 += 1
        allscore += getscore(getformatplan(plan))

    print 'onevariation_wait:' + str(num3)
    print 'better_wait:' + str(beginscore - allscore)
    return allscore


def findgoodplans(plans, goodplans):
    plans.sort(key=lambda plan: len(plan))
    # for plan in plans:
    #     length = len(plan)
    plan = plans[-1]
    length = len(plan)
    if length > 18:
        goodplans.append(plan)
        plans.remove(plan)


allplans = []
plan = []
reader = csv.reader(file('output/Riders1000score551878.csv', 'rU'))
lastline = ['D0001', 1]
for line in reader:
    if lastline[0] != line[0]:
        allplans.append(plan)
        lastline = line
        plan = []
        if '-' in line[4]:
            plan.append([line[5], 1])
        else:
            plan.append([line[5], 0])
    else:
        # print line
        # lastline = line
        if '-' in line[4]:
            plan.append([line[5], 1])
        else:
            plan.append([line[5], 0])
allplans.append(plan)

allplans = (1000 - len(allplans)) * [[]] + allplans
length = len(allplans)
print "length:", length

for plan in allplans:  # 打印allplans
    print plan

# 计算分数
allscore = 0
for plan in allplans:
    if plan != []:
        allscore += getscore(getformatplan(plan))
print "score:", allscore

localtime = int(time.time())
score = inheritance(allplans)
score = inheritance2(allplans)
# score = inheritancewait(allplans)

print '\n开始打印第一个文件\n'
csvfile = file('./output/chance' + str(localtime) + 'score' + str(score) + '.csv', 'wb')
writer = csv.writer(csvfile)

riders = []
for i in range(1, 10000):
    riders.append('D' + str(i).zfill(4))

i = 0
score = 0
print allplans
allplans.sort(key=lambda plan: len(plan), reverse=False)
for plan in allplans:
    if plan != []:
        formatplan = getformatplan(plan)  # 一个配送员的配送行程
        score += getscore(formatplan)
        for oneplan in formatplan:  # oneplan：一个订单的配送计划
            amount = oneplan[3]
            if '+' in amount:
                oneplan[3] = amount[1:]  # 如果是加号，则不显示
            oneplan.insert(0, riders[i])
            writer.writerow(oneplan)
        i += 1
csvfile.close()

minscore = 552000

n = 0
print '\n已经打印出第一个文件，继续打印\n'
while (1):
    while (score > minscore):
        print 'Final No' + str(n)
        print time.asctime(time.localtime(time.time()))
        score = inheritance(allplans)
        score = inheritance2(allplans)
        # score = inheritancewait(allplans)      # 考虑等待时间的变异

        print 'length:' + str(length)
        n += 1

    csvfile = file('./output/chance' + str(localtime) + 'score' + str(score) + '.csv', 'wb')
    writer = csv.writer(csvfile)

    riders = []
    for i in range(1, 10000):
        riders.append('D' + str(i).zfill(4))

    i = 0
    score = 0
    allplans.sort(key=lambda plan: len(plan), reverse=False)
    for plan in allplans:
        if plan != []:
            formatplan = getformatplan(plan)
            score += getscore(formatplan)
            for oneplan in formatplan:
                amount = oneplan[3]
                if '+' in amount:
                    oneplan[3] = amount[1:]
                oneplan.insert(0, riders[i])
                writer.writerow(oneplan)
            i += 1
    csvfile.close()

    minscore -= 200
    # minscore -= 50
    print '\n继续打印文件\n'
